package com.kevin.learn.leetcode;

import com.alibaba.fastjson.JSON;
import com.kevin.learn.domain.TreeNode;

public class 二叉树展开为链表 {
    public static void main(String[] args) {
        TreeNode treeNode = initData();

        flatten(treeNode);

        System.out.println(JSON.toJSON(treeNode));
    }


    // 定义：将以 root 为根的树拉平为链表
    public static void flatten(TreeNode root) {
        // base case
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);

        /**** 后序遍历位置 ****/
        // 1、左右子树已经被拉平成一条链表
        TreeNode left = root.left;
        TreeNode right = root.right;

        // 2、将左子树作为右子树
        root.left = null;
        root.right = left;

        // 3、将原先的右子树接到当前右子树的末端
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }
        p.right = right;
    }
    
    private static TreeNode initData() {
        TreeNode treeNode = new TreeNode(1);

        // 左
        TreeNode left2 = new TreeNode(2);
        TreeNode left4 = new TreeNode(4);


        left2.setLeft(left4);
        treeNode.setLeft(left2);

        // 右
        TreeNode right3 = new TreeNode(3);
        treeNode.setRight(right3);

        return treeNode;
    }
}
